The present invention relates generally to bi-level imaging, and more particularly to the generation of bi-level digital halftone images using threshold or "dither" matrices.
Pseudo-halftoning is a form of bi-level imaging which is used to represent continuous tone black and white or color images having, for example, areas of black, white and shades of gray (halftones) using only two output levels. The two output levels are no color (e.g. black) and color (e.g. white). With bi-level printing, shades of gray are represented by areas of dots, the size and number of which determine how gray a particular area is perceived by the human eye. The centers of the dots are usually aligned in a regular screen pattern.
Optical halftoning is used conventionally in lithography and photo-engraving. Black and white pictures in a newspaper are printed using optical halftoning and this screen pattern can be seen with a magnifying glass. When a pseudo-halftone negative is made from a continuous-tone copy, a halftone screen, such as an out-of-focus pattern of diffused dots and corresponding spaces, is placed in the light path between the camera lens and a sheet of high-contrast photographic film. The basic function of the halftone screen and the high-contrast photographic film is to create a diffraction pattern on the photographic film. The size of each spot on the film represents the average intensity of a small region in the original image. This process thus converts the halftones of the original continuous-tone copy into solid spots of equal density but varying size. As the intensity of the reflected light increases from shadows to highlights, the halftones of the continuous-tone copy produce intermediate size spots (pseudo-halftones) which the human eye perceives as shades of gray.
In digital halftoning the optical halftone screen is eliminated. Instead, numeric values representing the intensity at each picture element (PEL) of an input image are compared with a threshold value in order to make a black or white decision. A technique known as "spatial dithering" utilizes a variable-level threshold mask or dither matrix representing a two dimensional array of PEL storage positions, each containing an intensity threshold value. The term "dither" refers to the fact that the threshold values change from one position to the next, a technique which dramatically improves image quality over systems using only a single threshold value. To produce the bi-level image, the values in the threshold matrix storage positions are tested against corresponding PELs in the continuous tone input image. By use of the term "corresponding", it will be understood that a PEL from an input image may be tested against only one storage position in a threshold matrix, a sub-area of the matrix, an entire matrix, or a tiled area of the matrices. Each input PEL having an intensity value exceeding a corresponding value in the threshold matrix is printed. This printing produces an output image formed from a plurality of printed PEL patterns whose shape and size form a bi-level image corresponding to the original continuous tone image.
A technique known as ordered dithering is implemented by dividing the total input image area into a regular pattern of unit areas corresponding in size to, e.g., a single threshold or dither matrix. Each unit area includes a plurality of PELs (e.g. 256), but at typical printer resolutions on the order of 240 PELs per inch, the unit areas are very small and difficult to discern individually without magnification. A threshold matrix can be used like a small tile that covers each unit area of the input image and is repeated horizontally and vertically to compare the matrix threshold values with the intensity in each unit area. This comparison may be done with only a sub-area of the matrix, if necessary.
In ordered dithering, the manner in which the thresholding matrix is formed can have a dramatic effect on image quality. For example, the size of the thresholding matrix is proportional to the number of gray levels which can be represented, but is inversely proportional to image resolution and contrast. Image quality also depends on the arrangement of values in the threshold matrix. For example, high spatial resolution can be obtained by arranging the threshold values such that similar values are positioned as far as possible from one another in the threshold matrix. This arrangement results in a checker-board-like arrangement of PELs at intermediate intensity levels. The method, however, is susceptible to ink spread as when a printer cannot reliably deposit a single square PEL of ink. If a single PEL cannot be displayed or printed without spreading into an adjacent PEL position, the output will appear too dark. Also, since ink spreading does not produce a regular dot pattern, artifacts will be perceived in the image where dots happen to fall close together, especially when in vertical and horizontal rows. These are known as "worm" artifacts and can be quite distracting.
A method that compensates for ink spread is the "dot cluster" method. In this approach, similar threshold matrix values are arranged close to one another and so that increases of image intensity are represented by dot clusters of increasing size. This method of ordered dithering most closely simulates optical halftoning. Dot overlap is naturally compensated for such that the effects of ink spread are minimized.
Notwithstanding the advantages of the dot cluster method, the order in which the dot clusters are formed may significantly affect image quality. If the threshold matrices are not well balanced, and the order that the PELs are added to the dot clusters does not preserve symmetry, unevenly weighted dot clusters may be produced. For example, some threshold matrices are filled as spirals growing around a central point or filled as a rectangle from a side or a corner. This creates visually distracting shapes and patterns of dot clusters. Other matrices are filled in vertical and horizontal rows of dot clusters. Instead of perceived areas of different levels of gray, patterns are seen as vertical and horizontal rows of dots. This is particularly distracting because vertical and horizontal images are the orientations to which the human eye is most sensitive. The extent of this sensitivity is such that vertical and horizontal lines are perceived even when the lines are not true lines and are composed only of dashes or dots.
Thus, there is an evident need for a bi-level imaging method for producing black and white or color images wherein threshold matrices are provided to define dot clusters that are symmetrical and bi-laterally balanced, and wherein subjectively perceived horizontal and vertical lines, visually distracting shapes and patterns of dot clusters, and overly dark pictures resulting from dot spread are minimized. The method should further allow the formation of matrices of varying size in an efficient manner with minimal required processing time in order to adjust the range of intensity values that are resolved. For example, even though an input image is scanned so that eight bits are used to represent the intensity values, the actual values may range from 50 to 200 rather than the entire 256 level range possible with eight bits. In many situations, it is desirable to use a smaller matrix for the smaller range of actual values. Controlling matrix size may also be desirable in order to accommodate changes in input matrix size.
While there have been numerous prior art proposals relating to the formation of dither or threshold matrices, solutions satisfying the aforementioned objectives have not been forthcoming. For example, P. Stucki, "Advances In Digital Image Processing, Theory, Application, Implementation", pp. 201-214 (1979) discusses a digital halftone matrix based on clustered dot patterns. One such matrix is formed as an eight by eight array that includes four quadrants. There are two pairs of diagonally opposing quadrants having identical patterns. One pair of quadrants is filled outwardly from the quadrant centers while the other pair of quadrants is filled inwardly from the quadrant perimeters. The proposed matrix achieves a forty-five degree angle in the dot clusters and grows in a balanced and symmetrical manner. However, the size of the matrix is fixed and no procedure is defined for reproducing the matrix or to produce larger matrices. Moreover, dots are not consistently added in alternating subquadrant pairs. Accordingly, a threshold matrix overcoming the foregoing disadvantages and which is produced by a procedure permitting reproducibility and changes in matrix size would be desirable.